package al53maxsubArrays;

public class MaxSubArray {

    // O(n的平方) 被淘汰；
    public static int maxSubArray(int[] nums) {

        if (nums==null || nums.length == 0){
            return 0;
        }

        int max = nums[0];
        int subSum = nums[0];

        for(int i = 1;i<nums.length;i++){
            subSum = Math.max(nums[i],subSum+nums[i]);

            max = Math.max(subSum,max);
        }

        return max;
    }

    public static void main(String[] args) {
        int[] nums = {1,4,7,3,12,-4};
        int i = maxSubArray(nums);
        System.out.println(i);
    }
}
